Whiteline: delta/whiteline CD Series - delta.iso/tools/lernen/dicionar/source/btree.def

Modula Definition | 1995-11-25 | 5.5 KB | 139 lines

DEFINITION MODULE BTree;


CONST  Order = 42;
       (* Mit dieser Ordnung erhält man TSIZE(PageType) von 512 k *)
       nn = Order;
       n = (nn DIV 2);
       Empty= -1D;
       TreeRoot=0D;


TYPE (* TYPEn für den Bayer Baum *)


     FileType = ( TheData, NumIndex, GerIndex, PorIndex );
     (* Unterscheidung zwischen Daten und IndexFiles             *)
     (* und den verschiedenen IndexArten. Dieser AufzählungsTyp  *)
     (* wird vor allem für die Querverweisliste bei multiplen    *)
     (* Schlüsseln gebraucht (-> BaseType) => FileType so ordnen *)
     (* daß bei Next : ARRAY [FileType] keine unnötigen Einträge *)
     (* entstehen, d.h. zuerst alle IndexTypen die keine doppelten *)
     (* Schlüssel zulassen und dann die anderen (oder so ... ) *)


     KeyType = LONGCARD; (* Um diesen Typ zu ändern sind auch Anpassungen *)
                    (* im  IMPLEMENTATION MODULE nötig !!! *)

     EntryType = ARRAY [0..43] OF CHAR;

     DataType = RECORD
           Inhalt : ARRAY[0..4] OF EntryType;
           Flags  : ARRAY [0..5] OF CHAR;
        (* 0..3 werden verwendet, 4,5 sind nur FüllBytes *)
        (* um auf TSIZE(PageType) von 256 Bytes zu kommen *)
        END(*RECORD*);

     DataPtr = LONGINT; (* Zeigt auf die Lage der Daten im File *)

                        (* Wenn man DataPtr bzw. PagePtr auf INTEGER *)
                        (* ändern möchte sind einige Änderungen im  *)
                        (* IMPLEMENTATION MODULE notwendig! *)

     PagePtr = LONGINT; (* Position einer Seite im File *)

     KeyArray =  ARRAY [NumIndex..PorIndex] OF KeyType;

     BaseType = RECORD
          Flag : BOOLEAN;
          Next : ARRAY [GerIndex..PorIndex] OF DataPtr;
          (* Querverweisliste (doppelt verkettet) für die Verwendung *)
          (* von mehreren Einträgen pro Schlüssel *)
          Prev : ARRAY [GerIndex..PorIndex] OF DataPtr;
          Key  : KeyArray;
          (*Key  : ARRAY [NumIndex..PorIndex] OF KeyType;*)
          (* In diesem Feld werden sämtliche Schlüssel untergebracht *)
          Data : DataType;
        END(*RECORD*);

     ItemType = RECORD
           Key        : KeyType;
           RecordNr : DataPtr;
           Ptr        : PagePtr;
        END(*RECORD*);

     PageType = RECORD
           Flag : BOOLEAN;
           Anz    : CARDINAL;
           Ptr0 : PagePtr;
           Item : ARRAY [1..nn] OF ItemType;
        END(*RECORD*);


     FileOf = RECORD
(* Dieser Typ schleppt so ziemlich alles mit sich rum *)
(* was für die Verwaltung der Datei interressant ist *)
         Name : ARRAY [0..127] OF CHAR;
         (* Datei-Name *)
         Handle : INTEGER;
         (* GEMDOS- Filehandle *)
         CASE Type : FileType OF
         (* Je Nachdem ob es sich um ein Daten oder IndexFile *)
         (* handelt Pointer auf unterschiedliche Typen        *)
         (* Außerdem werden durch den Eintrag im TAG-Feld die *)
         (* verschiedenen Querverweislisten verwaltet         *)
                    TheData : RecordPtr : POINTER TO BaseType;
                    ELSE     RecordPtr1 : POINTER TO PageType;
                   END(*CASE*);
         RecordSize : LONGINT; (* LONG(TSIZE(Inhalt)) *)
         (* Länge eines Records *)
         Current : LONGINT;
         Last : LONGINT; (* PagePtr bzw DataPtr *)
         (* Letzter Eintrag in der Datei                  *)
         (* gibt gleichzeitig die Dateigröße in Records an *)
                 MultipleKeys : BOOLEAN;
                 (* Flag ob mehrere Einträge unter einem Schlüssel erlaubt sind *)
         END(*RECORD*);

    PrintDataProc = PROCEDURE( DataType);

(* for internal use only :   *)

PROCEDURE Get( VAR File : FileOf; Pos : LONGINT);
PROCEDURE Put( VAR File : FileOf; Pos : LONGINT);
(*
PROCEDURE FileLength(FileName : ARRAY OF CHAR; length : LONGINT) :BOOLEAN;
  *)



PROCEDURE Create(VAR File : FileOf); (* Eine neue Datei anlegen. Ist eine Datei dieses Namens schon vorhanden wird sie gelöscht *)
PROCEDURE Start(VAR File : FileOf); (* Datei Öfnen. Die Datei muß vorhanden sein !!! *)
PROCEDURE Close(VAR File: FileOf);  (* Datei Schließen. Wichtig sonst gehen alle Daten verloren !!*)

PROCEDURE PutData(VAR DataBase : FileOf; Data : DataType;  Reference : DataPtr);
PROCEDURE GetData(VAR DataBase : FileOf; VAR Data : DataType; VAR Keys : KeyArray; Reference :DataPtr);

PROCEDURE AddKey(VAR Index, DataBase : FileOf; NewKey : KeyType; Reference : DataPtr): BOOLEAN;
PROCEDURE AddData( VAR DataBase : FileOf; NewData : DataType) : DataPtr;

PROCEDURE Delete(VAR Index, DataBase : FileOf; Key : KeyType; VAR DataPointer : DataPtr): BOOLEAN;

PROCEDURE SearchPtr(VAR Index, DataBase : FileOf; Page : PagePtr; Key : KeyType; VAR found : BOOLEAN) : DataPtr;

PROCEDURE SearchFirst(VAR Index, DataBase : FileOf; Key : KeyType; VAR Data : DataType; VAR Keys : KeyArray): BOOLEAN;

PROCEDURE SearchNext(VAR Index, DataBase : FileOf; VAR Data : DataType; VAR Keys : KeyArray) : BOOLEAN;
PROCEDURE SearchPrevious(VAR Index, DataBase : FileOf; VAR Data : DataType;VAR Keys : KeyArray) : BOOLEAN;
(*   Suche bei Schlüsselgleichheit  *)

PROCEDURE First(VAR Index, DataBase : FileOf; VAR Key : KeyType; VAR Data : DataType; VAR Keys : KeyArray);
PROCEDURE Last (VAR Index, DataBase : FileOf; VAR Key : KeyType; VAR Data : DataType; VAR Keys : KeyArray);

PROCEDURE Next(VAR Index, DataBase : FileOf; Key : KeyType; VAR NextKey : KeyType; VAR NextData: DataType; VAR Keys : KeyArray) : BOOLEAN;
PROCEDURE Previous(VAR Index, DataBase : FileOf;  Key : KeyType; VAR NextKey : KeyType; VAR NextData: DataType; VAR Keys : KeyArray) : BOOLEAN;

PROCEDURE PrintTree(VAR Index, DataBase : FileOf; Tree : PagePtr; Tiefe : CARDINAL; OutProc : PrintDataProc);

END BTree.